#define DEBUG
#include <cstdio>
#include <cassert>
#define INF 0x7ffffff
#define MAXN 10000
#define MAXR 100000
#define MAXHEAPSIZE MAXN*10

using namespace std;

class Graph {
public:
  int n, m, ind[MAXN+1], to[MAXR+1], len[MAXR+1], link[MAXR+1], dis[MAXN+1];

  void addSide(int x, int y, int val) {
    m++;
    to[m] = y;
    len[m] = val;
    link[m] = ind[x];
    ind[x] = m;
  }

  void spfa(int s) {
    static int que[MAXN+1];
    static bool book[MAXN+1];
    for (int i=1; i<=n; i++) {
      dis[i] = INF;
    }
    dis[s] = 0;
    que[1] = s;
    for (int h=0, t=1; h!=t; ) {
      h = h%n+1;
      int x=que[h], y;
      book[x] = false;
      for (int i=ind[x]; i; i=link[i]) {
	y=to[i];
	if (dis[y]>dis[x]+len[i]) {
	  dis[y] = dis[x]+len[i];
	  if (!book[y]) {
	    t = t%n+1;
	    que[t] = y;
	    book[y] = true;
	  }
	}
      }
    }
  }
};

class Heap {
public:
  int a[MAXHEAPSIZE+1][3], size;

  bool cmp(int x, int y) {
    return a[x][0]<a[y][0] || (a[x][0]==a[y][0] && a[x][1]<=a[y][1]);
  }

  void swap(int x, int y) {
    int temp;
    for (int i=0; i<3; i++) {
      temp=a[x][i], a[x][i]=a[y][i], a[y][i]=temp;
    }
  }
  
  void up(int o) {
    if (o>1 && cmp(o, o>>1)) {
      swap(o, o>>1);
      up(o>>1);
    }
  }

  void down(int o) {
    if (((o<<1<size && cmp(o<<1, (o<<1)+1)) || (o<<1==size)) && cmp(o<<1, o)) {
      swap(o, o<<1);
      down(o<<1);
    } else if ((o<<1<size && cmp((o<<1)+1, o<<1)) && cmp((o<<1)+1, o)) {
      swap(o, (o<<1)+1);
      down((o<<1)+1);
    }
  }

  void push(int x, int y, int z) {
    size++;
    a[size][0] = x, a[size][1]=y, a[size][2] = z;
    up(size);
  }

  void pop() {
    swap(1, size);
    size--;
    down(1);
  }
};

int main() {
#ifdef DEBUG
  freopen("1163.in", "r", stdin);
  freopen("1163.out", "w", stdout);
#endif

  static Graph g, ug;
  int n, r, k;
  scanf("%d %d %d", &n, &r, &k);
  g.n = ug.n = n;
  for (int i=1; i<=r; i++) {
    int x, y, len;
    scanf("%d %d %d", &x, &y, &len);
    char ch;
    while (ch = getchar(),ch != 10);
    g.addSide(x, y, len);
    ug.addSide(y, x, len);
  }
  ug.spfa(n);

  static Heap que;
  que.push(ug.dis[1], 0, 1);
  int len=0;
  for (; que.size; ) {
    int x=que.a[1][2], v=que.a[1][1];
    que.pop();
    if (x==n) {
      if (len<v) {
	k--;
	len = v;
      }
      if (!k) {
	printf("%d", v);
	return 0;
      }
    }
    for (int i=g.ind[x]; i; i=g.link[i]) {
      que.push(v+g.len[i]+ug.dis[g.to[i]], v+g.len[i], g.to[i]);
    }
  }

  fcloseall();
  return 0;
}
